// 链表结构 ---  start
class LinkNode {
  constructor(value) {
    this.val = value;
    this.next = null;
  }
}
// 链表结构 ---  end

// 测试用demo1  [1,3,5]
let demo1 = new LinkNode(1);
demo1.next = new LinkNode(3);
demo1.next.next = new LinkNode(5);
// 测试用demo2  [2,4,6]
let demo2 = new LinkNode(2);
demo2.next = new LinkNode(4);
demo2.next.next = new LinkNode(6);

// 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 解题思路： 设置一个“哨兵节点”叫 pHead，整体流程如下：

// - 如果 pHead1 和 pHead2，均没遍历完：
//     - 如果 pHead1.val <= pHead2.val，那么当前 node 的 next 指向 pHead1。并且移动 pHead1 指针。
//     - 否则，当前 node 的 next 指向 pHead2，移动 pHead2 指针。
//     - 移动 node 指针
//     - 继续循环
// - 否则，结束循环：
//     - 如果 pHead1 未遍历完，node 的 next 指向 pHead1
//     - 如果 pHead2 未遍历玩，node 的 next 指向 pHead2

// 时间复杂度是 O(N)，空间复杂度是 O(1)。代码如下：
function Merge(pHead1, pHead2) {
  // write code here
  if (!pHead1) {
    // 如果pHead1链表不存在，就返回pHead2
    return pHead2;
  }
  if (!pHead2) {
    // 如果pHead2链表不存在，就返回pHead1
    return pHead1;
  }
  // 新建一个‘哨兵节点’
  let pHead = new LinkNode(-1);
  // 头节点的指针
  let node = pHead;

  while (pHead1 && pHead2) {
    // pHead1 和 pHead2 都存在时
    if (pHead1.val <= pHead2.val) {
      node.next = pHead1;
      pHead1 = pHead1.next;
    } else {
      node.next = pHead2;
      pHead2 = pHead2.next;
    }
    node = node.next;
  }

  if (pHead1) {
    // pHead1 链表长度大于 pHead2
    node.next = pHead1;
  }
  if (pHead2) {
    // pHead2 链表长度大于 pHead1
    node.next = pHead2;
  }
  // pHead是-1，所以是pHead.next
  return pHead.next;
}

// console.log(Merge(demo1, demo2));
let res = Merge(demo1, demo2);

// 输出合并后的链表内容
while (res) {
  console.log(res.val);
  res = res.next;
}
